Math'φsics

Menu
  • Acceuil
  • Maths
  • Physique
    • Maths
    • Physique
  • Problème dual

    Formulaire de report


    Problème dual \((Q)\)
    Problème consistant à maximiser \(G_*\) avec le Lagrangien du Problème primal. $$\text{Trouver }\alpha\in D\text{ tq }G_*(\alpha)=\sup_D G_*$$
    • on note \(v(Q)\) \(:=\sup_D G_*\) la valeur du problème dual


    START
    Théorème
    Résolution du Problème primal à partir du Problème dual Hypothèses:
    • \(\alpha_*\) est une solution de \((Q)\)
    • les contraintes \(c\) sont continues
    • \(\exists V\in\mathcal V(\alpha_*)\) dans \(D\) et \(x:V\to U\) Fonction continue tq \(\forall\alpha\in V\), \(x(\alpha)\) est solution du problème : $$\text{Trouver }x\in U,\quad\mathcal L(x,\alpha)=G_*(\alpha)$$

    Résultats:
    • \(x(\alpha_*)\) est solution du Problème primal \((P)\)
    • \((x(\alpha_*),\alpha_*)\) est un Point selle du Lagrangien \(\mathcal L\)
    •     
    • (en particulier, il n'y a pas de Saut de dualité)

    Equivalence?:
    Résumé:
    END

    Exercices

    Calculer le problème dual du problème : $$\min_x c^Tx\quad\text{ avec }\quad Ax=b,x\geqslant0$$

    Calculer le Lagrangien.

    Calculer \(G_*(\lambda,\mu)\) : c'est un \(\inf\) \(\to\) vérifier pour quelles valeurs des contraintes \(\lambda,\mu\) la valeur de \(x\) n'est pas simplifiée.

    Le problème dual revient donc à maximiser la quantité dans le cas fini, avec la contrainte associée (⚠ \(\mu\) doit être positif !).


    Calculer le problème dual du problème : $$\max_y b^Ty\quad\text{ avec }\quad A^Ty\leqslant c$$

    Calculer le lagrangien associé.

    Calculer \(G_*(\lambda,\mu)\), en faisant attention aux cas où les \(y\) s'annulent.

    Le problème dual revient à maximiser dans le cas \(\ne-\infty\), avec la contrainte associée.


    Calculer le problème dual du problème : $$\min_{x,y}c^Tx-b^Ty\quad\text{ avec }\quad Ax=b,x\geqslant0,A^Ty\leqslant c$$

    Calculer le lagrangien.

    Calculer \(G_*(\lambda,\mu_1,\mu_2)\) (vérifier le cas où les \(x,y\) s'annulent).

    En déduire la valeur à maximiser et la contrainte.



    L'existence vient du Théorème de Weierstrass.

    L'unicité vient de la convexité stricte.

    La qualification vient du fait qu'on est sur une boule.



    Calculer le lagrangien et son gradient en \(x\).

    En déduire la valeur de \(x\) nécessaire à l'annulation de ce gradient.

    Le problème dual est donc de maximiser le laplacien en ce point \(x\).


    Calculer le problème dual du problème : $$\underset{x^2+3y^2\leqslant1}{\min_{(x,y)\in{\Bbb R}^2} }2x+3y$$

    Exprimer le lagrangien.
    $$\mathcal L((x,y),\mu)=2x+3y+\mu(x^2+3y^2-1)$$

    Si \(\mu=0\), alors le lagrangien est affine et son \(\inf\) est \(-\infty\).
    $$G_*( \mu)=\begin{cases}-\infty&\text{si}\quad \mu=0\\ ???&\text{sinon.}&\end{cases}$$

    Dans le cas contraire, on a un polynôme convexes, qu'on peut minimiser en dérivant en \(x\) et en \(y\).
    $$\frac\partial{\partial x}\mathcal L((x,y),\mu)=2+2\mu x\quad\text{ et }\quad\frac\partial{\partial y}\mathcal L((x,y),\mu)=3+6\mu y$$
    On peut donc minimiser en prenant \((x,y)=(-\frac1\mu,-\frac1{2\mu})\).

    $$G_*( \mu)=\begin{cases}-\infty&\text{si}\quad \mu=0\\ \mathcal L((-\frac1\mu,-\frac1{2\mu}),\mu)=\frac{-7}{4\mu}-\mu&\text{sinon.}&\end{cases}$$
    4i : Calculer la valeur de \(G_*(\mu)\) dans ce cas.

    Conclusion : exprimer la valeur du problème dual.

    Le problème dual est donc : $$\max_{\mu\geqslant0}\frac{-7}{4\mu}-\mu$$


  • Rétroliens :
    • Machine linéaire
    • Problème dual
    • Problème primal